package com.atguigui.leetcode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 648.单词替换
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/7/7 8:34
 */
public class P648ReplaceWords {

    public static void main(String[] args) {
        Solution solution = new P648ReplaceWords().new Solution();
        // TO TEST
    }

    class Solution {

        /**
         * 执行用时：195 ms, 在所有 Java 提交中击败了18.28%的用户
         * 内存消耗：45.2 MB, 在所有 Java 提交中击败了89.75%的用户
         *
         * @param dictionary
         * @param sentence
         * @return
         */
        public String replaceWords(List<String> dictionary, String sentence) {

            Set<String> dictionarySet = new HashSet<String>();
            for (String root : dictionary) {
                dictionarySet.add(root);
            }

            String[] words = sentence.split(" ");
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                //遍历每个字符的字符
                for (int j = 0; j < word.length(); j++) {
                    //如果map中有，直接退出循环
                    if (dictionarySet.contains(word.substring(0, 1 + j))) {
                        words[i] = word.substring(0, 1 + j);
                        break;
                    }
                }
            }

            return String.join(" ", words);
        }
    }
}
